#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
int dis[N][N];
int n, m;
void floyd()
{
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	memset(dis, 0x3f, sizeof(dis));
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		dis[a][b] = dis[b][a] = min(dis[a][b], c);
	}
	floyd();
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (dis[1][i] == 0x3f3f3f3f) {
			res = -1;
			break;
		}
		else {
			res = max(res, dis[1][i]);
		}
	}
	cout << res << endl;
	return 0;
}